//
// Description: 84. 柱状图中最大的矩形
// Created by Loading on 2022/3/10.
//

#include <bits/stdc++.h>

using namespace std;

int largestRectangleArea(vector<int> &heights) {
    /* 遍历每个高度，找到左侧和右侧第一个比此高度小的位置停止，区间面积就是当前高度的最大面积 */
    int n = heights.size();
    // 表示左侧和右侧的第一个比当前高度小的位置下标，-1或n 为无
    vector<int> left(n), right(n);
    // 单调栈
    stack<int> stk;
    // 寻找左侧
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && heights[stk.top()] >= heights[i]) {
            stk.pop();
        }
        left[i] = stk.empty() ? -1 : stk.top();
        stk.push(i);
    }

    stk = stack<int>();
    // 寻找右侧
    for (int i = n - 1; i >= 0; --i) {
        while (!stk.empty() && heights[stk.top()] >= heights[i]) {
            stk.pop();
        }
        right[i] = stk.empty() ? n : stk.top();
        stk.push(i);
    }

    // 计算最大面积
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res = max(res, (right[i] - left[i] - 1) * heights[i]);
    }

    return res;
}

int main() {
    vector<int> heights{1, 1};
    int res = largestRectangleArea(heights);
    cout << res << endl;

    return 0;
}